package com.chj.zhongji.class04;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;

public class Code01_ChooseWork {

	public static class Job {
		public int money;
		public int hard;

		public Job(int money, int hard) {
			this.money = money;
			this.hard = hard;
		}
	}

	public static class JobComparator implements Comparator<Job> {
		@Override
		public int compare(Job o1, Job o2) {
			return o1.hard != o2.hard ? (o1.hard - o2.hard) : (o2.money - o1.money);
		}
	}

	public static int[] getMoneys(Job[] job, int[] ability) {
		Arrays.sort(job, new JobComparator());
		System.out.println("-----job----");
		for (int i = 0; i < job.length; i++) {
			System.out.println(job[i].hard + "------" + job[i].money);
		}
		System.out.println("----job-----");
		// 难度为key的工作，最优钱数是多少，有序表
		TreeMap<Integer, Integer> map = new TreeMap<>();
		map.put(job[0].hard, job[0].money);
		Job pre = job[0]; // pre 之前组的组长
		for (int i = 1; i < job.length; i++) {
			if (job[i].hard != pre.hard && job[i].money > pre.money) {
				pre = job[i];
				map.put(pre.hard, pre.money);
			}
		}

		Iterator iter = map.entrySet().iterator();
		while (iter.hasNext()) {
			Map.Entry entry = (Map.Entry) iter.next();
			int key = (Integer) entry.getKey();
			int eg = (Integer) entry.getValue();
			System.out.println("---hard---: " + key + " ---money---: " + eg);
		}

		int[] ans = new int[ability.length];
		for (int i = 0; i < ability.length; i++) {
			Integer key = map.floorKey(ability[i]);
			System.out.println("---key---: " + key + " ---ability[i]---: " + ability[i]);
			ans[i] = key != null ? map.get(key) : 0;
		}
		return ans;
	}

	public static void getMoneys2() {
		int n = 3;// n表示工作的数量
		int m = 3;// m表示同学的数量

		// jobs数组 n行2列 n行表示n个工作，第一列表示工作的难度， 第二列表示工作的报酬
		int[][] jobs = new int[][] { { 1, 100 }, { 10, 1000 }, { 10, 990 }, { 1000000000, 1001 } };

		// jobs数组排序
		Arrays.sort(jobs, ((o1, o2) -> o1[0] - o2[0]));// 按照工作难度从小到大排序
		System.out.println("----jobs[i][1]-----");
		for (int i = 0; i < jobs.length; i++) {
			System.out.println(jobs[i][1]);
		}
		System.out.println("-----jobs[i][1]----");
		// 很重要 我们把每个工作的报酬设置为 难度比他小的这些工作中的最大报酬
		for (int i = 1; i < jobs.length; i++) {
			jobs[i][1] = Math.max(jobs[i - 1][1], jobs[i][1]);
		}

		System.out.println("----jobs[i][1]-----");
		for (int i = 0; i < jobs.length; i++) {
			System.out.println(jobs[i][1]);
		}
		System.out.println("-----jobs[i][1]----");

		// 将job数组存储到TreeMap中，其中，key=难度，value=最大报酬
		TreeMap<Integer, Integer> map = new TreeMap<>();
		for (int i = 0; i < jobs.length; i++) {
			map.put(jobs[i][0], jobs[i][1]);
		}

		Iterator iter = map.entrySet().iterator();
		while (iter.hasNext()) {
			Map.Entry entry = (Map.Entry) iter.next();
			int key = (Integer) entry.getKey();
			int eg = (Integer) entry.getValue();
			System.out.println("---hard---: " + key + " ---money---: " + eg);
		}

		int[] abilitys = new int[] { 9, 10, 1000000000 };
		// 输入每个同学的能力ability
		for (int i = 0; i < m; i++) {
			int ability = abilitys[i];
			// 返回的是小于等于ability的最大key，其实这里就是在找这个能力下的最大工作难度
			Integer key = map.floorKey(ability);
			if (key != null)
				// 找到这个难度对应的最大报酬就是我们想得到的最大报酬
				System.out.println(map.get(key));
			else
				System.out.println(0);
		}
	}

	public static void main(String[] args) {
		TreeMap<Integer, String> map = new TreeMap<>();
		map.put(7, "我是7");
		map.put(3, "我是3");
		map.put(9, "我是9");
		map.put(2, "我是2");
		map.put(8, "我是8");
		map.put(5, "我是5");
		System.out.println(map.containsKey(2));
		System.out.println(map.get(7));
		map.remove(9);

		System.out.println(map.firstKey());
		System.out.println(map.lastKey());
		// <= num 离num最近的东西
		System.out.println("floorKey: " + map.floorKey(6));
		// >= num 离num最近的东西
		System.out.println("ceilingKey: " + map.ceilingKey(6));

		System.out.println("---------");
		// 时间复杂度全是O(logN)级别
		Job jb01 = new Job(100, 1);
		Job jb02 = new Job(1000, 10);
//		Job jb04 = new Job(1002, 10);
		Job jb03 = new Job(1001, 1000000000);
		Job[] jobs = new Job[] { jb01, jb02, jb03 };

		int[] ability = new int[] { 9, 10, 1000000000 };
		int[] mm = getMoneys(jobs, ability);
		for (int i = 0; i < mm.length; i++) {
			System.out.println(mm[i]);
		}
		System.out.println("getMoneys2");
		getMoneys2();
	}

	// https://blog.csdn.net/Haidaiya/article/details/105475404
}
